
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// class Solution {
//     int tmp[50010];
// public:
//     int reversePairs(vector<int>& nums) {
//         return MergeSort(nums,0,nums.size()-1);
//     }

//     int MergeSort(vector<int>& nums, int left, int right)
//     {
//         if(left >= right) return 0;  //只有一个数字,构不成逆序对

//         int ret = 0;
//         int mid = (left+right)>>1;
//         //[left,mid] [mid+1,right] 分别计算左右逆序对的个数
//         ret+=MergeSort(nums,left,mid);
//         ret+=MergeSort(nums,mid+1,right);

//         //cur1,cur2用来遍历分治的左右两部分,i遍历tmp,记录这两个部分的正确合并
//         int cur1=left,cur2=mid+1,i=0;
//         while(cur1 <= mid && cur2<=right)
//         {
//             //记录一左一右有多少逆序对,固定cur2,找到第一个大于它的cur1
//             if(nums[cur1]<=nums[cur2])
//             {
//                 tmp[i++]=nums[cur1++];
//             }
//             else
//             {
//                 ret+=mid-cur1+1;
//                 tmp[i++]=nums[cur2++];
//             }
//         }
//         //只剩下一部分时说明一左一右已经找完了
//         while(cur1<=mid)  tmp[i++]=nums[cur1++];
//         while(cur2<=right)  tmp[i++]=nums[cur2++];

//         //还原nums
//         for(int j=left; j<=right; j++)
//         {
//             nums[j] = tmp[j-left];
//         }
//         return ret;
//     }
// };

// class Solution
// {
//     vector<int> tmp, tmp_index, value, index;

// public:
//     vector<int> countSmaller(vector<int> &nums)
//     {
//         int n = nums.size();
//         tmp.resize(n);
//         tmp_index.resize(n);
//         value.resize(n);
//         for (int i = 0; i < n; i++)
//         {
//             index.push_back(i);
//         }
//         MergeSort(nums, 0, n - 1);
//         return value;
//     }

//     void MergeSort(vector<int> &nums, int left, int right)
//     {
//         if (left >= right)
//             return;

//         int mid = (left + right) >> 1;
//         //[left,mid] [mid+1,right]
//         //处理左右情况
//         MergeSort(nums, left, mid);
//         MergeSort(nums, mid + 1, right);

//         //处理一左一右的情况
//         int cur1 = left, cur2 = mid + 1, i = 0;
//         while (cur1 <= mid && cur2 <= right) //降序
//         {
//             if (nums[cur1] <= nums[cur2])
//             {
//                 tmp_index[i] = index[cur2]; //下标和nums绑定,跟着nums一起修改
//                 tmp[i++] = nums[cur2++];
//             }
//             else
//             {
//                 tmp_index[i] = index[cur1];
//                 value[index[cur1]] += right - cur2 + 1;  //重点,找到它原来的下标
//                 tmp[i++] = nums[cur1++];
//             }
//         }

//         //处理边界
//         while (cur1 <= mid)
//         {
//             tmp_index[i] = index[cur1];
//             tmp[i++] = nums[cur1++];
//         }
//         while (cur2 <= right)
//         {
//             tmp_index[i] = index[cur2];
//             tmp[i++] = nums[cur2++];
//         }

//         // 还原nums,index也要还原
//         for (int j = left; j <= right; j++)
//         {
//             index[j] = tmp_index[j - left];
//             nums[j] = tmp[j - left];
//         }
//     }
// };

// class Solution
// {
//     vector<int> tmp;

// public:
//     int reversePairs(vector<int> &nums)
//     {
//         int n = nums.size();
//         tmp.resize(n);

//         return mergeSort(nums, 0, n - 1);
//     }

//     int mergeSort(vector<int> &nums, int left, int right)
//     {
//         if (left >= right)
//             return 0;

//         int ret = 0;
//         int mid = (left + right) >> 1;
//         //[left,mid] [mid+1,right]
//         ret += mergeSort(nums, left, mid);
//         ret += mergeSort(nums, mid + 1, right);

//         // 在合并数组前先计算翻转对
//         int cur1 = left, cur2 = mid + 1, i = 0;
//         while (cur1 <= mid && cur2 <= right) // 降序
//         {
//             if (nums[cur1] / 2.0 <= nums[cur2])
//             {
//                 cur2++;
//             }
//             else
//             {
//                 ret += right - cur2 + 1;
//                 cur1++;
//             }
//         }

//         cur1 = left, cur2 = mid + 1, i = 0;
//         while (cur1 <= mid && cur2 <= right) // 降序
//         {
//             if (nums[cur1] <= nums[cur2])
//             {
//                 tmp[i++] = nums[cur2++];
//             }
//             else
//             {
//                 tmp[i++] = nums[cur1++];
//             }
//         }

//         // 处理剩下的边界情况
//         while (cur1 <= mid)
//         {
//             tmp[i++] = nums[cur1++];
//         }
//         while (cur2 <= right)
//         {
//             tmp[i++] = nums[cur2++];
//         }

//         // 合并两个有序数组
//         for (int j = left; j <= right; j++)
//         {
//             nums[j] = tmp[j - left];
//         }
//         return ret;
//     }
// };